// 107. 二叉树的层序遍历 II
// https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
// 中等,给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历。
// （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
// 示例 1：
// 输入：root = [3,9,20,null,null,15,7]
// 输出：[[15,7],[9,20],[3]]
// 示例 2：
// 输入：root = [1]
// 输出：[[1]]
// 示例 3：
// 输入：root = []
// 输出：[]

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int> > levelOrder;
        if (!root) {
            return levelOrder;
        }
        queue<TreeNode*> quNode;
        quNode.push(root);
        while(!quNode.empty()) {
            int size = quNode.size();
            vector<int> level;
            for (int i = 0; i<size; i++) {
                TreeNode* node = quNode.front();
                level.push_back(node->val);
                quNode.pop();
                if (node->left) {
                    quNode.push(node->left);
                }
                if (node->right) {
                    quNode.push(node->right);
                }
            }
            levelOrder.push_back(level);
        }
        reverse(levelOrder.begin(),levelOrder.end());
        return levelOrder;
    }
};

int main() {
	return 0;
}
